package pro11_20.pro13;

import utils.linkedlist.LinkNode;

/**
 * @author yaohuaiying
 * @create 2018-02-09 13:17
 *
 * 第13题（链表）：
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct LinkNode
{
int m_nKey;
LinkNode* m_pNext;
};

思路
    长度-k个酱紫嘛 这个好像是最简单的 先找出长度 在去找倒数多少个
    遍历了两次
    或者倒序一下链表 同样有问题

    因为事先不知道长度 所以至少要遍历一遍
    e......写了一个求长度的函数 我好像想到了
    在遍历求长度的时候，返回的时候判断一下就不ok了
先试一下
 **/
public class Main {
    public static void main(String[] args){
        LinkNode head = new LinkNode(0);
        head.insertNode(head ,1);
        head.insertNode(head ,2);
        head.insertNode(head ,3);
        head.insertNode(head ,4);
        head.insertNode(head ,5);
        head.insertNode(head ,6);
        head.insertNode(head ,7);
        head.insertNode(head ,8);
        getK(head,3);
        LinkNode.nodePrint(head);
        System.out.println();
        System.out.println(kNode.getData());
        System.out.println("length:" +  LinkNode.getLength(head));
    }

    static LinkNode kNode = null;
    public static int getK(LinkNode currentNode,int k){
        if(currentNode == null){
            return 0;
        }
        int n = getK(currentNode.getNext(), k) + 1;
        if(n == k){
            kNode = currentNode;
        }
        return n;
    }
}
